class P151 {

	public static void main( String[ ] args ) {

		int[ ] values = new int[ 101 ];
		values[13] = 1;
		values[15] = 10;
		values[16] = 11;
		values[17] = 7;
		values[18] = 17;
		values[19] = 11;
		values[20] = 15;
		values[22] = 5;
		values[23] = 21;
		values[24] = 13;
		values[26] = 14;
		values[27] = 11;
		values[28] = 23;
		values[29] = 22;
		values[30] = 9;
		values[32] = 17;
		values[34] = 7;
		values[36] = 15;
		values[38] = 22;
		values[40] = 24;
		values[41] = 30;
		values[42] = 9;
		values[43] = 38;
		values[44] = 15;
		values[46] = 27;
		values[47] = 9;
		values[49] = 38;
		values[50] = 22;
		values[51] = 19;
		values[53] = 38;
		values[54] = 53;
		values[58] = 20;
		values[59] = 9;
		values[60] = 22;
		values[61] = 7;
		values[62] = 21;
		values[65] = 41;
		values[66] = 10;
		values[69] = 64;
		values[73] = 67;
		values[74] = 19;
		values[75] = 66;
		values[77] = 52;
		values[78] = 24;
		values[79] = 22;
		values[81] = 10;
		values[82] = 57;
		values[85] = 41;
		values[86] = 70;
		values[87] = 60;
		values[89] = 81;
		values[90] = 79;
		values[91] = 55;
		values[93] = 49;
		values[94] = 5;
		values[95] = 22;
		values[96] = 54;
		values[97] = 52;
		values[99] = 15;
		
		String line = readLn();
		while (!"0".equals(line)) {
			System.out.println(values[Integer.parseInt(line)]);
			line = readLn();
		}
	}
	
	static String readLn() {
        String newLine = System.getProperty("line.separator");
        StringBuffer buffer = new StringBuffer();
        int car = -1;
        try {
            car = System.in.read();
            while ((car > 0) && (car != newLine.charAt(0))) {
                buffer.append((char)car);
                car = System.in.read();
            }
            if (car == newLine.charAt(0))
            System.in.skip(newLine.length() - 1);
        } catch (java.io.IOException e) { return (null);}
        if ((car < 0) && (buffer.length() == 0)) return (null);
        return (buffer.toString()).trim();
    }
}
